package com.sx.sx1.lintcode.day717;

import java.util.HashMap;
import java.util.PriorityQueue;

public class LC197 {

    static class Solution {
        /**
         * @param a: An array of integers
         * @return: A long integer
         */
        public long permutationIndex(int[] a) {
            //经验
            int size = a.length;
            long ans=1l,fact=1l;
            for (int i = size-1; i >=0 ; i--) {
                int cnt =0;
                for (int j = i+1; j <size ; j++) {
                    if(a[j]<a[i]) cnt++;
                }
                ans+= fact*cnt;
                fact*=(size-i);
            }
            return ans;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.permutationIndex(new int[]{1,2,4}));
        System.out.println(obj.permutationIndex(new int[]{3,2,1}));
    }


    static class LC19701 {

        public static void main(String[] args) {
            test1();
            test2();
        }

        static void test1(){
            int[] arr3={18,17,16,15,14,13,12,1,11,9,8,7,6,5,4,1,3,2,1};
            int[] arr={4,1,3,2,1};
            System.out.println(new LC19701().permutationIndex(arr));  // 6
        }

        static void test2(){
            int[] arr={1,2,4};
            //System.out.println(new LC197().permutationIndex(arr)); // 1
        }
        public long permutationIndex(int[] a) {
            // write your code here
            //fun1(a);
            System.out.println(fun2(a));
            System.out.println("----------------------------------");
            return fun3(a);
        }


        static class Info{
            long cnt = 0;
        }
        //当对数器使用，超过内存限制。
        public static long fun1(int[] a){

            PriorityQueue<String> t = new PriorityQueue<>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <a.length ; i++) {
                sb.append(a[i]);
            }
            Info info = new Info();
            dfs(a,0,info,sb.toString());

            System.out.println(info.cnt);
            return info.cnt;
        }


        public static void dfs(int[] arr,int index, Info info ,String target){
            if(index == arr.length){
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i <arr.length ; i++) {
                    sb.append(arr[i]);
                }

                String tmp = sb.toString();
                if(tmp.compareTo(target) <0){
                    info.cnt++;
                }else if(tmp.compareTo(target) ==0){
                    info.cnt++;
                }
                return;
            }

            for (int i = index; i <arr.length ; i++) {
                swap(arr,i,index);
                dfs(arr,index+1,info,target);
                swap(arr,i,index);
            }
        }

        public static void swap(int[] arr,int i,int j){
            int t=  arr[i];
            arr[i] = arr[j];
            arr[j] =t;
        }

        //4,1,3,2,1
        public static long fun2(int[] arr){
            int size =  arr.length;
            if(size ==0) return 0;
            long ans =1l,fac=1l;
            for (int i = size-1; i >=0 ; i--) {
                int cnt = 0;
                for (int j = i+1; j <size ; j++) {
                    if(arr[j]< arr[i]) cnt++;
                }

                ans += fac*cnt;
                fac*=(size-i);
            }

            return ans;
        }

        public static long fun3(int[] arr){
            int n = arr.length;
            if(n ==0) return 0;

            HashMap<Integer,Integer> map = new HashMap<>();
            for (int i = n-1; i >=0 ; i--) {
                int cnt = 0;
                for (int j = i+1; j <n ; j++) {
                    if(arr[j] < arr[i]){
                        cnt++;
                    }
                }

                map.put(i,cnt);
            }

            long ans = 1l;
            for (int i = 0; i <n ; i++) {
                long fact = 1l;
                for (int j = n-i-1; j >0 ; j--) {
                    fact=fact*j;
                }
                ans = ans+(fact*(map.get(i)));
            }

            return ans;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有203条未读消息，请及时查看
197 · 排列序号
算法
中等
通过率
39%

题目
题解15
笔记
讨论99+
排名
记录
描述
给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入:[1,2,4]
输出:1
样例 2:

输入:[3,2,1]
输出:6
相关知识
学习《九章算法班随课教程》课程中的6.13如何求一个排列是第几个排列相关内容 ，了解更多相关知识！
标签
相关题目

51
上一个排列
中等
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
